#include <iostream>
#include <cassert>

using namespace std;
int fibonacci(int n);
int f(int);

int main(){
	int n = 6;
	int res = fibonacci(n);
	int res2 = f(n);
	cout << res << "\t" << res2 <<  endl;
	return 0;
}


/**
 * 
 *	数学归纳法
 *  参考资料 : 主定理
 */
int fibonacci(int n){
	assert(n >= 1);
	if(n == 1 || n == 2)
		return 1;
	return fibonacci(n - 1) + fibonacci(n - 2);
}

/**
 *  20 + 21 + .. +2n = 2(n+1) -1 幂  O(2^n)
 *  使用递归树
 *  n 在 20 时是百万级计算量
 *  优化 ： 剪枝  动态规划
 *  对比 ： 归并排序  分治算法
		1. 树深度是log(n) 不是上面的 n
		2. 每个节点处理数据规模越来越小，每一层数据是n ,每个节点是O(n)级别算法 有logn层
 */
int f(int n){
	assert(n >= 0);
	if(n == 0){
		return 1;
	}
	return f(n - 1) + f(n - 1);
}
